/**
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 */
public class Test5 {

    public static void main(String[] args) {
        System.out.println(longestPalindrome("wwwe"));
    }
    public static String longestPalindrome(String s) {

        if (s.length() == 1) return s;
        int len = s.length();

        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }

        char[] chars = s.toCharArray();
        int start = 0;
        int maxLen = 1;

        for (int L = 2; L <= len; L++) {
            for (int i = 0; i < len; i++) {
                int left = i;
                int right = i+L-1;
                if (right >= len) break;

                if (chars[left] == chars[right]){
                    if (L == 2){
                        dp[left][right] = true;
                    }else{
                        dp[left][right] = dp[left+1][right-1];
                    }

                    if (dp[left][right] && (right-left+1 > maxLen)){
                        maxLen = right-left+1;
                        start = left;
                    }
                }
            }
        }
        return s.substring(start,start+maxLen);
    }
}
